package primary.primary0;

import java.util.*;

/**
 * 图, 环, 图找环, 并查集, TreeSet, 去重
 */
public class S0684冗余连接 {
    /**
     * 5, 可以了。
     * 树中节点多了一个边, 必定会出现一个环, 因为树中不同节点之间都是连通的。
     * 注意: 只要是无环图, 就必定是树(未必是二叉树, 并且树还是有向的), 所以找到环, 然后删掉环中任意一个, 都可以让整体变回树
     * 找环: 从任一个节点, 遍历图, 整个visited, 都可以找到环。找环之前需要对无向图进行存储。
     *      因为是无向图中的环, 所以边只能用一次。
     *
     */
    public static int[] findRedundantConnection(int[][] edges) {
        int totalNum = edges.length;
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for(int[] edge : edges){
            // 存储图, 因为是无向的, 所以两个方向都存
            Set<Integer> curList = graph.getOrDefault(edge[0], new HashSet<>());
            curList.add(edge[1]);
            graph.put(edge[0], curList);
            Set<Integer> curList2 = graph.getOrDefault(edge[1], new HashSet<>());
            curList2.add(edge[0]);
            graph.put(edge[1], curList2);
        }
        // 深度优先, 那么在找到环的时候, 我们会拿到这么个环, 每个边用一次就销毁, 销毁是双向的
        Deque<Integer> circle = new LinkedList<>();
        boolean[] visited = new boolean[totalNum + 1];
        circle.add(1);
        visited[1] = true;
        findCircle(visited, circle, graph); // 找到环, 记录在circle里
        // 这个是有一个环, 但是相当于是一个线上拉了一个环, 所以需要把这个线截断。
        int circleEnd = circle.peekLast();
        while(!circle.isEmpty() && circle.peekFirst() != circleEnd){
            circle.pollFirst();
        }
        // 要返回最后一个出现的, 所以要给出现的排个序, 上面那个graph是对图的存储, 没有边的顺序
        // 我们反过来, 找最后一个出现在环里的边, 但是怎么用边做key是个问题。
        // 不用kv来找, 我们从后往前遍历edge, 看看edge的边在不在circle的边的set里, 但是这个set里相同值的边也是不同的值
        // 需要自定义Comparator, 那么即不是无序的hashSet, 需要有序的TreeSet

        // 注意这里的TreeSet, 一定要严谨, 就对半开, 对称, 比较两者, 如果两个元素按照不同顺序进来, 它们的大小关系也一定是固定的,
        // 就不能省略这里的  && a[1] - b[1] > 0) 。
        Set<int[]> circleSet = new TreeSet<>((int[] a, int[] b)->{
            if(a[0] - b[0] != 0){
                return a[0] - b[0];
            }else{
                return a[1] - b[1];
            }
        });
        List<Integer> circleList = new ArrayList<>(circle);
        int[] res = new int[2];
        for(int i = 0; i < circleList.size() - 1; i++){
            int[] circleEle = new int[2];
            circleEle[0] = circleList.get(i);
            circleEle[1] = circleList.get(i + 1);
            circleSet.add(circleEle);
            int[] circleEle2 = new int[2];
            circleEle2[0] = circleList.get(i + 1);
            circleEle2[1] = circleList.get(i);
            circleSet.add(circleEle2);
        }

        for(int i = edges.length - 1; i >= 0; i--){
            if(circleSet.contains(edges[i])) {
                return edges[i];
            }
        }

        return null;
    }
    public static boolean findCircle(boolean[] visited, Deque<Integer> circle, Map<Integer, Set<Integer>> graph){
        Set<Integer> nextLevel = graph.getOrDefault(circle.getLast(), new HashSet<>());
        Integer[] nextLevelList = new Integer[nextLevel.size()];
        nextLevel.toArray(nextLevelList);
        if(nextLevel.size() == 0) return false;
        for(int i: nextLevelList){
            if(visited[i]){
                // 找着环了
                circle.addLast(i);
                return true;
            }
            visited[i] = true;
            graph.get(circle.getLast()).remove(i);
            graph.get(i).remove(circle.getLast());
            circle.addLast(i);
            if(findCircle(visited, circle, graph)){
                return true;
            }
            circle.pollLast();
            visited[i] = false;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{new int[]{2, 7}, new int[]{7, 8}, new int[]{3, 6}, new int[]{2, 5}, new int[]{6, 8}, new int[]{4, 8}, new int[]{2, 8}, new int[]{1, 8}, new int[]{7, 10}, new int[]{3, 9}};
        System.out.println("res: " + Arrays.toString(new S0684冗余连接().findRedundantConnection(edges)));
    }
}
